package com.dyz.leetcode._19_greedy;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Map;

public class _322_coinChange {
    public int coinChange(int[] coins, int amount) {

        List<Integer> cs = new ArrayList<>();
        List<List<Integer>> res = new ArrayList<>();
        dfs(amount, coins, cs, res);

        if(res.size()==0){return -1;}

        int min = res.get(0).size();
        for (int i = 1; i < res.size(); i++) {
            if(res.get(i).size()<min){
                min = res.get(i).size();
            }
        }
        return min;
    }

    private void  dfs(int target, int[] c, List<Integer> coins, List<List<Integer>> res){
        if(target<0){
            return;
        }
        if(target==0){
            res.add(new ArrayList<>(coins));
            return;
        }
        for (int i = 0; i < c.length; i++) {
            coins.add(c[i]);
            dfs(target-c[i], c, coins, res);
            coins.remove(coins.size()-1);

        }
    }
    //优化
    private int minCount = 0;
    private void  dfs(int target, int[] c, List<Integer> coins){
        if(target<0){
            return;
        }
        if(target==0){
            minCount = Math.min(minCount, coins.size());
            return;
        }
        for (int i = 0; i < c.length; i++) {
            coins.add(c[i]);
            dfs(target-c[i], c, coins);
            coins.remove(coins.size()-1);
        }
    }


    //剪枝
    public int coinChange1(int[] coins, int amount) {
        List<Integer> cs = new ArrayList<>();
        Arrays.sort(coins);
        dfs1(amount, coins, cs);
        return minCount==0?-1:minCount;
    }
    private void dfs1(int target, int[] c, List<Integer> coins){
        if(target==0){
            minCount = Math.min(minCount, coins.size());
            return;
        }
        for (int i = c.length-1; i < c.length; i++) {
            if(target-c[i]<0){continue;}
            coins.add(c[i]);
            dfs(target-c[i], c, coins);
            coins.remove(coins.size()-1);
        }
    }
}
